The present invention relates to the field of data placement in distributed computing systems. More particularly, the present invention relates to data placement for fault tolerance in distributed computing systems.
Many computing systems take the form of a distributed system in which processing capability and data storage capacity are distributed in a network. Typically, nodes of the network each include a processor and data storage. The data placed at any given node may be accessed locally, for use by the processor at the node, or remotely, for use by the processor of another node.
In such a distributed environment, consideration must be given to the placement and replication of data in the system. At one extreme, a single copy of a data object, such as a file, may be placed in the network. However, if many nodes need to access the data object, such an arrangement may result in unacceptably high levels of traffic directed to the node having the single copy of the data and may also result in unacceptably low reliability should a failure occur at that node. At another extreme, the data object may be replicated at every node. This arrangement, however, may result in an unacceptable level of traffic associated with updating the data at every node in order to maintain consistency whenever changes to the data occur and may also result in unacceptable cost of storage capacity needed to store all the data copies in the system.
For a distributed system, the ideal placement of data will depend upon a variety of factors, such as the number and sizes of data objects, the frequency in which objects are accessed or changed, the number and distance between nodes that require access to the same data, desired performance levels and desired tradeoffs between cost, performance and reliability. Due to the complexity of the problem, algorithms for data placement have been largely based on heuristics.
In addition, prior algorithms for determining a placement of data in a distributed system have typically ignored the issue of fault-tolerance. Accordingly, such systems are unlikely to meet performance requirements in the event of failures that inevitably occur in a distributed system. While some prior algorithms have taken fault-tolerance into account, these solutions also have disadvantages in that they tend to be computationally intractable for systems having more than a few nodes. Another disadvantage is that such solutions have been applicable only to a specific type of distributed system and load and, thus, lack general applicability.
Therefore, what is needed is a technique for data placement in a distributed system that has more general applicability than prior techniques and that takes into account fault-tolerance. It is to these ends that the present invention is directed.